﻿namespace Leetcode.N0057;
public class Solution
{

    public int[][] Insert(int[][] intervals, int[] newInterval)
    {
        var findX = this.FindX(intervals, newInterval[0]);
        var findY = this.FindY(intervals, findX.index, newInterval[1]);
        var list = new List<int[]>();

        for (int i = 0; i < findX.index; i++)
        {
            list.Add(intervals[i]);
        }

        list.Add(new int[] { findX.maxX, findY.maxY });

        for (int i = findY.index + 1; i < intervals.Length; i++)
        {
            list.Add(intervals[i]);
        }

        return list.ToArray();
    }

    private (int index, int maxX) FindX(int[][] intervals, int x)
    {
        var from = 0;
        var to = intervals.Length - 1;
        while (from <= to)
        {
            var m = from + (to - from) / 2;
            var item = intervals[m];

            if (x < item[0])
            {
                to = m - 1;
            }
            else if (x > item[1])
            {
                from = m + 1;
            }
            else
            {
                return (m, Math.Min(item[0], x));
            }
        }
        return (from, x);
    }

    private (int index, int maxY) FindY(int[][] intervals, int fromIndex, int y)
    {
        var from = fromIndex;
        var to = intervals.Length - 1;
        while (from <= to)
        {
            var m = from + (to - from) / 2;
            var item = intervals[m];

            if (y < item[0])
            {
                to = m - 1;
            }
            else if (y > item[1])
            {
                from = m + 1;
            }
            else
            {
                return (m, Math.Max(item[1], y));
            }
        }
        return (from - 1, y);
    }
}